package leetcode; /**
 * description:
 * author:zt
 * date:2021-08-31
 */

/**
 * 给你一个整数 n ，请你找出并返回第 n 个 丑数 。
 *
 * 丑数 就是只包含质因数 2、3 和/或 5 的正整数。
 */
public class leetcode264 {
    public static void main(String[] args) {
        System.out.println(new leetcode264().nthUglyNumber(10));
    }
    public int nthUglyNumber(int n) {
        int[] dp = new int[n];
        int index2=0, index3=0, index5=0;
        int i = 1;
        dp[0] = 1;
        while (i<n){
            int a = 2*dp[index2]; int b = 3*dp[index3]; int c = 5*dp[index5];
            dp[i] = Math.min(Math.min(a,b),c);
            if (dp[i]==a) index2++;
            if (dp[i]==b) index3++;
            if (dp[i]==c) index5++;
            i++;
        }

        return dp[n-1];
    }
}
